// iterator standard header -*-c++-*-
// Copyright 2003-2010 IAR Systems AB. 
#ifndef _ITERATOR_
#define _ITERATOR_

#ifndef _SYSTEM_BUILD
#pragma system_include
#endif

#include <xutility>
_STD_BEGIN

// TEMPLATE CLASS back_insert_iterator
template<class _Container>
class back_insert_iterator
  : public _Outit
{       // wrap pushes to back of container as output iterator
public:
  typedef _Container container_type;
  typedef typename _Container::const_reference const_reference;
  typedef typename _TypeUtil::_ParameterType<const_reference>::_Type _ParamTy;

  explicit back_insert_iterator(_Container& _Cont)
    : container(&_Cont)
  {}      // construct with container

  back_insert_iterator<_Container>& operator=(_ParamTy _Val)
  {       // push value into container
    container->push_back(_Val);
    return (*this); 
  }

  back_insert_iterator<_Container>& operator*()
  {       // pretend to return designated value
    return (*this); 
  }

  back_insert_iterator<_Container>& operator++()
  {       // pretend to preincrement
    return (*this); 
  }

  back_insert_iterator<_Container> operator++(int)
  {       // pretend to postincrement
    return (*this); 
  }

protected:
  _Container *container;  // pointer to container
};

// TEMPLATE FUNCTION back_inserter
template<class _Container> inline
back_insert_iterator<_Container> back_inserter(_Container& _Cont)
{       // return a back_insert_iterator
  return (_STD back_insert_iterator<_Container>(_Cont)); 
}

// TEMPLATE CLASS front_insert_iterator
template<class _Container>
class front_insert_iterator
  : public _Outit
{       // wrap pushes to front of container as output iterator
public:
  typedef _Container container_type;
  typedef typename _Container::const_reference const_reference;
  typedef typename _TypeUtil::_ParameterType<const_reference>::_Type _ParamTy;

  explicit front_insert_iterator(_Container& _Cont)
    : container(&_Cont)
  {}      // construct with container

  front_insert_iterator<_Container>& operator=(_ParamTy _Val)
  {       // push value into container
    container->push_front(_Val);
    return (*this); 
  }

  front_insert_iterator<_Container>& operator*()
  {       // pretend to return designated value
    return (*this); 
  }

  front_insert_iterator<_Container>& operator++()
  {       // pretend to preincrement
    return (*this); 
  }

  front_insert_iterator<_Container> operator++(int)
  {       // pretend to postincrement
    return (*this); 
  }

protected:
  _Container *container;  // pointer to container
};

// TEMPLATE FUNCTION front_inserter
template<class _Container> inline
front_insert_iterator<_Container> front_inserter(_Container& _Cont)
{       // return front_insert_iterator
  return (_STD front_insert_iterator<_Container>(_Cont)); 
}

// TEMPLATE CLASS insert_iterator
template<class _Container>
class insert_iterator
  : public _Outit
{       // wrap inserts into container as output iterator
public:
  typedef _Container container_type;
  typedef typename _Container::const_reference const_reference;
  typedef typename _TypeUtil::_ParameterType<const_reference>::_Type _ParamTy;

  insert_iterator(_Container& _Cont, typename _Container::iterator _Where)
    : container(&_Cont), iter(_Where)
  {}      // construct with container and iterator

  insert_iterator<_Container>& operator=(_ParamTy _Val)
  {       // insert into container and increment stored iterator
    iter = container->insert(iter, _Val);
    ++iter;
    return (*this); 
  }

  insert_iterator<_Container>& operator*()
  {       // pretend to return designated value
    return (*this); 
  }

  insert_iterator<_Container>& operator++()
  {       // pretend to preincrement
    return (*this); 
  }

  insert_iterator<_Container>& operator++(int)
  {       // pretend to postincrement
    return (*this); 
  }

protected:
  _Container *container;  // pointer to container
  typename _Container::iterator iter;     // iterator into container
};

// TEMPLATE FUNCTION inserter
template<class _Container,
         class _Iter> inline
insert_iterator<_Container> inserter(_Container& _Cont, _Iter _Where)
{       // return insert_iterator
  return (_STD insert_iterator<_Container>(_Cont, _Where)); 
}

// TEMPLATE CLASS istream_iterator
template<class _Ty,
         class _Elem = char,
         class _Traits = char_traits,
         class _Diff = ptrdiff_t>
class istream_iterator
  : public iterator<input_iterator_tag, _Ty, _Diff,
  const _Ty *, const _Ty&>
{       // wrap _Ty extracts from input stream as input iterator
public:
  typedef istream_iterator<_Ty, _Elem, _Traits, _Diff> _Myt;
  typedef _Elem char_type;
  typedef _Traits traits_type;
  typedef istream istream_type;

  istream_iterator()
    : _Myistr(0)
  {}      // construct singular iterator

  istream_iterator(istream_type& _Istr)
    : _Myistr(&_Istr)
  {       // construct with input stream
    _Getval(); }

  const _Ty& operator*() const
  {       // return designated value
    return (_Myval); 
  }

  const _Ty *operator->() const
  {       // return pointer to class object
    return (&**this); 
  }

  _Myt& operator++()
  {       // preincrement
    _Getval();
    return (*this); 
  }

  _Myt operator++(int)
  {       // postincrement
    _Myt _Tmp = *this;
    _Getval();
    return (_Tmp); 
  }

  bool _Equal(const _Myt& _Right) const
  {       // test for iterator equality
    return (_Myistr == _Right._Myistr); 
  }

protected:
  void _Getval()
  {       // get a _Ty value if possible
    if (_Myistr != 0 && !(*_Myistr >> _Myval))
      _Myistr = 0; 
  }

  istream_type *_Myistr;  // pointer to input stream
  _Ty _Myval;     // lookahead value (valid if _Myistr is not null)
};

// istream_iterator TEMPLATE OPERATORS
template<class _Ty, class _Elem, class _Traits, class _Diff> inline
bool operator==(
  const istream_iterator<_Ty, _Elem, _Traits, _Diff>& _Left,
  const istream_iterator<_Ty, _Elem, _Traits, _Diff>& _Right)
{       // test for istream_iterator equality
  return (_Left._Equal(_Right)); 
}

template<class _Ty, class _Elem, class _Traits, class _Diff> inline
bool operator!=(
  const istream_iterator<_Ty, _Elem, _Traits, _Diff>& _Left,
  const istream_iterator<_Ty, _Elem, _Traits, _Diff>& _Right)
{       // test for istream_iterator inequality
  return (!(_Left == _Right)); 
}

// TEMPLATE CLASS ostream_iterator
template<class _Ty, class _Elem = char,
         class _Traits = char_traits >
class ostream_iterator
  : public _Outit
{       // wrap _Ty inserts to output stream as output iterator
public:
  typedef _Elem char_type;
  typedef _Traits traits_type;
  typedef ostream ostream_type;

  ostream_iterator(ostream_type& _Ostr,
                   const _Elem *_Delim = 0)
    : _Myostr(&_Ostr), _Mydelim(_Delim)
  {}      // construct from output stream and delimiter

  ostream_iterator<_Ty, _Elem, _Traits>& operator=(const _Ty& _Val)
  {       // insert value into output stream, followed by delimiter
    *_Myostr << _Val;
    if (_Mydelim != 0)
      *_Myostr << _Mydelim;
    return (*this); 
  }

  ostream_iterator<_Ty, _Elem, _Traits>& operator*()
  {       // pretend to return designated value
    return (*this); 
  }

  ostream_iterator<_Ty, _Elem, _Traits>& operator++()
  {       // pretend to preincrement
    return (*this); 
  }

  ostream_iterator<_Ty, _Elem, _Traits> operator++(int)
  {       // pretend to postincrement
    return (*this); 
  }

protected:
  const _Elem *_Mydelim;  // pointer to delimiter string (NB: not freed)
  ostream_type *_Myostr;  // pointer to output stream
};

// TEMPLATE FUNCTION _Val_type
#pragma basic_template_matching
template<class _Iter> inline
typename iterator_traits<_Iter>::value_type *_Val_type(_Iter)
{       // return value type from arbitrary argument
  return (0); 
}

// TEMPLATE FUNCTION advance
#pragma basic_template_matching
template<class _InIt, class _Diff> inline
void advance(_InIt& _Where, _Diff _Off)
{       // increment iterator by offset, arbitrary iterators
  _Advance(_Where, _Off, _Iter_cat(_Where)); 
}

#pragma basic_template_matching
template<class _InIt, class _Diff> inline
void _Advance(_InIt& _Where, _Diff _Off, input_iterator_tag)
{       // increment iterator by offset, input iterators
  for (; 0 < _Off; --_Off)
    ++_Where; 
}

#pragma basic_template_matching
template<class _FI, class _Diff> inline
void _Advance(_FI& _Where, _Diff _Off, forward_iterator_tag)
{       // increment iterator by offset, forward iterators
  for (; 0 < _Off; --_Off)
    ++_Where; 
}

#pragma basic_template_matching
template<class _BI, class _Diff> inline
void _Advance(_BI& _Where, _Diff _Off, bidirectional_iterator_tag)
{       // increment iterator by offset, bidirectional iterators
  for (; 0 < _Off; --_Off)
    ++_Where;
  for (; _Off < 0; ++_Off)
    --_Where; 
}

#pragma basic_template_matching
template<class _RI, class _Diff> inline
void _Advance(_RI& _Where, _Diff _Off, random_access_iterator_tag)
{       // increment iterator by offset, random-access iterators
  _Where += _Off; 
}

// TEMPLATE FUNCTION _Dist_type
#pragma basic_template_matching
template<class _Iter> inline
typename iterator_traits<_Iter>::difference_type
*_Dist_type(_Iter)
{       // return distance type from arbitrary argument
  return (0); 
}

_STD_END
#endif /* _ITERATOR_ */

/*
 * This file is derived from software bearing the following
 * restrictions:
 *
 * Copyright (c) 1994
 * Hewlett-Packard Company
 *
 * Permission to use, copy, modify, distribute and sell this
 * software and its documentation for any purpose is hereby
 * granted without fee, provided that the above copyright notice
 * appear in all copies and that both that copyright notice and
 * this permission notice appear in supporting documentation.
 * Hewlett-Packard Company makes no representations about the
 * suitability of this software for any purpose. It is provided
 * "as is" without express or implied warranty.
 */

/*
 * Copyright (c) 1992-2009 by P.J. Plauger.  ALL RIGHTS RESERVED.
 * Consult your license regarding permissions and restrictions.
 V5.04:0576 */
